package Hot100.Medium.GreedyAndDP.DynamicPlanning;

import Hot100.Easy.LC94.TreeNode;

public class LC96_DifferentBST {
    public static void main(String[] args) {

    }

    public int numTrees(int n){
        // dp[i]数组含义：从1到i节点一共能组成的二叉搜索树的个数
        int[] dp = new int[n + 1];
        // 确定dp数组初始化值,由于左右子树组合遵循乘法原理，因此dp[0]应该是1而不是0
        dp[0] = 1;
        // 确定递推公式，并确定遍历顺序应该是从前往后，dp[i] = dp[i] + dp[j -1] * dp[i - j],其中j从1到i进行遍历
        for(int i = 0; i <= n; i++){
            for(int j = 1; j <= i; j++){
                dp[i] = dp[i] + dp[j - 1] * dp[i - j];
            }
        }
        return dp[n];
    }
}
